class Solution:
    def printNumbers(self, n: int) -> List[int]:
        return [i+1 for i in range(10**n-1)]
'''
利用dfs进行全排列
表示大数的变量类型：
无论是 short / int / long ... 任意变量类型，数字的取值范围都是有限的。因此，大数的表示应用字符串 String 类型。

2. 生成数字的字符串集：
使用 int 类型时，每轮可通过 +1+1 生成下个数字，而此方法无法应用至 String 类型。
并且， String 类型的数字的进位操作效率较低，例如 "9999" 至 "10000" 需要从个位到千位循环判断，进位 4 次。
观察可知，生成的列表实际上是 nn 位 00 - 99 的 全排列 ，因此可避开进位操作，通过递归生成数字的 String 列表。

3. 递归生成全排列：
基于分治算法的思想，先固定高位，向低位递归，当个位已被固定时，添加数字的字符串。
例如当 n = 2n=2 时（数字范围 1 - 991−99 ），固定十位为 00 - 99 ，按顺序依次开启递归，固定个位 00 - 99 ，
终止递归并添加数字字符串。
'''
class Solution:
    def printNumbers(self, n: int) -> [int]:
        def dfs(x):
            if x == n:  # 终止条件：已固定完所有位
                res.append(''.join(num))  # 拼接 num 并添加至 res 尾部
                return
            for i in range(10):  # 遍历 0 - 9
                num[x] = str(i)  # 固定第 x 位为 i
                dfs(x + 1)  # 开启固定第 x + 1 位
        num = ['0'] * n  # 起始数字定义为 n 个 0 组成的字符列表
        res = []  # 数字字符串列表
        dfs(0)  # 开启全排列递归
        return ','.join(res)  # 拼接所有数字字符串，使用逗号隔开，并返回


class Solution:
    def printNumbers(self, n: int) -> [int]:
        def dfs(x):
            if x == n:
                s = ''.join(num[self.start:])
                if s != '0': res.append(int(s))
                # 所有位都为 9 的判断条件可用以下公式
                if n - self.start == self.nine:
                    self.start -= 1
                return
            for i in range(10):
                if i == 9:
                    self.nine += 1
                num[x] = str(i)
                dfs(x + 1)
            # 在回溯前恢复 nine = nine - 1
            self.nine -= 1

        num, res = ['0'] * n, []
        self.nine = 0
        # 声明变量 startstart 规定字符串的左边界，以保证添加的数字字符串 num[start:] 中无高位多余的 0。
        # 例如当 n = 2时， 1−9 时 start = 1,10−99 时 start = 0
        #
        self.start = n - 1
        dfs(0)
        return res

